package com.example.find;

import java.util.*;


public class FindSolution2 {

    /**
     * 寻找出现频率最高的K个元素
     * @param nums
     * @param k
     * @return
     */
    public static List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        //先统计每个数字出现的次数，这个貌似不可避免，时间复杂度为O(n)
        for (int i = 0; i < nums.length; i++) {
            Integer count = map.get(nums[i]);
            if (null == count) {
                count = 0;
            }
            map.put(nums[i], count + 1);
        }
        //然后应该可以使用优先队列了
        PriorityQueue<Integer> queue = new PriorityQueue<>(k, new CustomerComparator(map));
        for (Integer integer : map.keySet()) {
            if (queue.size() < k) {
                queue.add(integer);
                continue;
            }
            int small = queue.peek();
            if (map.get(small) < map.get(integer)) {
                queue.poll();
                queue.add(integer);
            }
        }
        return new ArrayList<>(queue);
    }

    static class CustomerComparator implements Comparator<Integer> {
        Map<Integer, Integer> map;

        public CustomerComparator(Map<Integer, Integer> map) {
            this.map = map;
        }

        @Override
        public int compare(Integer o1, Integer o2) {
            return map.get(o1) - map.get(o2);
        }
    }

    static boolean arrayInvalid = false;

    /**
     * 找出数组中重复超过一半的数
     */
    public static int moreHalf(int[] nums, int length) {
        if (chechInvalidArray(nums, length)) {
            return 0;
        }
        int middle = length >> 1;
        int start = 0;
        int end = length - 1;
        int index = partition(nums, length, start, end);
        // 寻找中位数
        while (index != middle) {
            // 如果得到index大于中间值，则往前半部分查找
            if (index > middle) {
                end = index - 1;
                index = partition(nums, length, start, end);
            } else {
                start = index + 1;
                index = partition(nums, length, start, end);
            }
        }
        int result = nums[middle];
        if (!checkMoreThanHalf(nums, length, result)) {
            return 0;
        }
        return result;
    }

    public static boolean chechInvalidArray(int[] nums, int length) {
        arrayInvalid = false;
        if (nums == null && length <= 0) {
            arrayInvalid = true;
        }
        return arrayInvalid;
    }

    public static int partition(int[] nums, int length, int start, int end) {
        return -1;
    }

    public static boolean checkMoreThanHalf(int[] nums, int length, int target) {
        int times = 0;
        for (int i = 0; i < length; i++) {
            if (nums[i] == target) {
                times++;
            }
        }
        boolean isMoreThanHalf = true;
        if (times * 2 <= length) {
            arrayInvalid = true;
            isMoreThanHalf = false;
        }
        return isMoreThanHalf;
    }

    public static void main(String[] args) {
//        int[] nums = new int[] {1,2,3,2,2,2,5,4,2};
//        moreHalf(nums, nums.length);
        int[] arrayDemo = {1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 5, 5, 5, 5, 5, 5, 5, 5, 8};
        List<Integer> list = topKFrequent(arrayDemo, 2);
        list.forEach(i -> System.out.println(i));
    }

}
